LeetCode 24、两两交换链表中的节点

一、题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 两两交换链表中的节点（LeetCode 24）： https://leetcode.cn/problems/swap-nodes-in-pairs/ 
class Solution {
    public ListNode swapPairs(ListNode head) {

        // 寻找递归终止条件
        // 1、head 指向的结点为 null 
        // 2、head 指向的结点的下一个结点为 null 
        // 在这两种情况下，一个节点或者空节点无论怎么交换操作，都是原来的 head
      	if( head == null || head.next == null) {
       			return head;
    			}
  
        // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点或者最后两个节点
    		ListNode subHead = swapPairs(head.next.next);

        // 对于 head 这个节点来说，它是和它相邻的右边这个节点进行交换操作
        // 所以先要保存这个节点，并且经过上述递归终止条件的判断，head.next 是必然存在的
        ListNode headNext = head.next;

        // head 原来是指向 headNext
        // 交换之后
        // headNext 指向 head
    		headNext.next = head;
  
        // headNext 原来是指向 subHead
        // 现在需要让 head 指向 subHead
    		head.next = subHead;
  
        // 交换之后，原来的第二位的那个节点 headNext 变成了第一位
        // 把它返回就行
    		return headNext;
    }
}

**2、C++ **代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {

        // 寻找递归终止条件
        // 1、head 指向的结点为 null 
        // 2、head 指向的结点的下一个结点为 null 
        // 在这两种情况下，一个节点或者空节点无论怎么交换操作，都是原来的 head
       if( head == NULL || head->next == NULL) {
          		return head;
       }
  
        // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点或者最后两个节点
      	ListNode *subHead = swapPairs(head->next->next);

        // 对于 head 这个节点来说，它是和它相邻的右边这个节点进行交换操作
        // 所以先要保存这个节点，并且经过上述递归终止条件的判断，head.next 是必然存在的
        ListNode *headNext = head->next;

        // head 原来是指向 headNext
        // 交换之后
        // headNext 指向 head
      	headNext->next = head;
  
        // headNext 原来是指向 subHead
        // 现在需要让 head 指向 subHead
      	head->next = subHead;
  
        // 交换之后，原来的第二位的那个节点 headNext 变成了第一位
        // 把它返回就行
      	return headNext;
        
    }
};

3、Python 代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        # 寻找递归终止条件
        # 1、head 指向的结点为 null 
        # 2、head 指向的结点的下一个结点为 null 
        # 在这两种情况下，一个节点或者空节点无论怎么交换操作，都是原来的 head
        if head == None or head.next == None :
            return head

        # 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点或者最后两个节点
        subHead = self.swapPairs(head.next.next)

        # 对于 head 这个节点来说，它是和它相邻的右边这个节点进行交换操作
        # 所以先要保存这个节点，并且经过上述递归终止条件的判断，head.next 是必然存在的
        headNext = head.next

        # head 原来是指向 headNext
        # 交换之后
        # headNext 指向 head
        headNext.next = head
  
        # headNext 原来是指向 subHead
        # 现在需要让 head 指向 subHead
        head.next = subHead
  
        # 交换之后，原来的第二位的那个节点 headNext 变成了第一位
        # 把它返回就行
        return headNext

复杂度分析

时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。

空间复杂度：O(n)，其中 n 是链表的节点数量。空间复杂度主要取决于递归调用的栈空间。